import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {

    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> multi_stack = new LinkedList<>();
        LinkedList<String> res_stack = new LinkedList<>();
        for (Character c:s.toCharArray()) {
            if (c == '[') {
                multi_stack.addLast(multi);
                res_stack.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int k = multi_stack.removeLast();
                for (int i = 0; i < k;i++) tmp.append(res);
                res = new StringBuilder(res_stack.removeLast() + tmp);
            }else if(c >= '0' && c <= '9'){
                multi = multi * 10 + Integer.parseInt(c + "");
            }else {
                res.append(c);
            }
        }
        return res.toString();
    }

    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        int[] ret = new int[n];
        for (int i = 0;i < n - 1;i++) {
            for (int j = i + 1;j < n;j++) {
                if (temperatures[j] > temperatures[i]) {
                    ret[i] = j - i;
                    break;
                }
            }
        }
        return ret;
    }

    public int[] dailyTemperatures2(int[] temperatures) {
        int n = temperatures.length;
        int[] ret = new int[n];
        for (int i = n - 2;i >= 0;i--) {
            for (int j = i + 1;j < n;j+=ret[j]) {
                if (temperatures[j] > temperatures[i]) {
                    ret[i] = j - i;
                    break;
                }else if (ret[j] == 0) {
                    ret[i] = 0;
                    break;
                }
            }
        }
        return ret;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int n = temperatures.length;
        int[] ret = new int[n];
        for (int i = 0;i < n;i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                ret[index] = i - index;
            }
            stack.push(i);
        }
        return ret;
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<>();
        for (int i = 0;i < intervals.length;i++) {
            int l = intervals[i][0], r = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < l) {
                merged.add(new int[]{l, r});
            }else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], r);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public void setZeroes(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        boolean[] col = new boolean[m];
        boolean[] row = new boolean[n];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (matrix[i][j] == 0) {
                    col[j] = row[i] = true;
                }
            }
        }
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (col[j] || row[i]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> path = new ArrayList<>();
            int size = queue.size();
            for (int i = 0;i < size;i++) {
                TreeNode node = queue.poll();
                path.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(path);
        }
        return ret;
    }

    int count;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    public void dfs (TreeNode root) {
        if (root == null) return;
        dfs (root.left);
        count--;
        if (count == 0) {
            ret = root.val;
            return;
        }
        dfs (root.right);
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right){
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums,left , mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null) return ret;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0;i < size;i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    ret.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return ret;
    }

    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        dfs(root, 0, ret);
        return ret;
    }
    public void dfs(TreeNode root , int depth, List<Integer> ret) {
        if (root == null) return;
        if (depth == ret.size()) {
            ret.add(root.val);
        }
        dfs(root.right, depth + 1,ret);
        dfs(root.left, depth + 1, ret);
    }

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int ret = rootSum (root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }
    public int rootSum(TreeNode root, long targetSum) {
        int ret = 0;
        if (root == null) return 0;

        int val = root.val;
        if (val == targetSum) {
            ret ++;
        }
        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;
        Map<TreeNode,TreeNode> parentMap = new HashMap<>();
        Deque<TreeNode> stack = new LinkedList<>();
        parentMap.put(root, null);
        stack.push(root);
        while (!stack.isEmpty() && !(parentMap.containsKey(p)&&parentMap.containsKey(q))) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                stack.push(node.left);
                parentMap.put(node.left, node);
            }
            if (node.right != null) {
                stack.push(node.right);
                parentMap.put(node.right,node);
            }
        }
        Set<TreeNode> pAncestors = new HashSet<>();
        while (p != null) {
            pAncestors.add(p);
            p = parentMap.get(p);
            if (p == q) {
                return q;
            }
        }
        while (!pAncestors.contains(q)) {
            q = parentMap.get(q);
        }
        return q;
    }

    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1;i <= amount;i++) {
            for (int j = 0;j < coins.length;j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        boolean cur = false;
        if (root.val > pre) cur = true;
        pre = root.val;
        boolean right = isValidBST(root.right);
        return cur&&left&&right;
    }

    public int rob (int[] nums) {
        // write code here
        int n = nums.length;
        return Math.max(nums[0] + rob(nums, 2, n - 2), rob(nums, 1, n - 1));
    }
    public int rob(int[] nums, int start, int end) {
        if (start > end) return 0;
        int[][] dp = new int[nums.length][2];
        dp[start][0] = nums[start];
        for (int i = start + 1;i <= end;i++) {
            dp[i][0] = dp[i - 1][1] + nums[i];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        return Math.max(dp[end][0], dp[end][1]);
    }

    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int[][] memo;
    int n, m;
    public int longestIncreasingPath(int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        memo = new int[n][m];
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                ret = Math.max(ret, dfs(matrix, i, j));
            }
        }
        return ret;
    }
    public int dfs (int[][] matrix,int i,int j) {
        if (memo[i][j] != 0) return memo[i][j];
        int ret = 1;
        for (int k = 0;k < 4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0&&x < n&&y >= 0&&y < m&&matrix[x][y] > matrix[i][j]) {
                ret = Math.max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }

    public boolean isSubsequence(String s, String t) {
        int l1 = s.length(),l2 = t.length();
        int i = 0,k = 0;
        while (i < l1&&k < l2) {
            if (s.charAt(i) == t.charAt(k)) {
                i++;
            }
            k++;
        }
        return i == l1;
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0;i < nums.length;i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int aim = sum / 2;
        boolean[][] dp = new boolean[nums.length + 1][aim + 1];
        for (int i = 0;i <= nums.length;i++) {
            dp[i][0] = true;
        }
        for (int i = 1;i <= nums.length;i++) {
            for (int j = 1;j <= aim;j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][aim];
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0 ;i < nums.length;i++) {
            sum += nums[i];
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = (sum + target)/2 + 1;
        if (n < 0) {
            return 0;
        }
        int[][] dp = new int[nums.length + 1][n];
        dp[0][0] = 1;
        for (int i = 1;i <= nums.length;i++) {
            for (int j = 0; j < n;j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }

        }
        return dp[nums.length][n-1];
    }

    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0;
        for (int i = citations.length - 1;i >= 0;i--) {
            if (citations[i] > h) {
                h++;
            }
            else break;
        }
        return h;
    }

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            //证明右边的路是下坡路，不一定有坡峰
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                //这里是右边的路是上坡路
                left = mid + 1;
            }
        }
        return right;
    }

    public int maxDiff(int num) {
        String str = String.valueOf(num);
        int n = str.length();
        int a = 0;
        for (int i = 0;i < n;i++) {
            if (str.charAt(i) != '9') {
                a = Integer.parseInt(str.replace(str.charAt(i), '9'));
                break;
            }
        }
        if (a == 0) a = num;
        int b = 0;
        boolean found = false;
        if (str.charAt(0) != '1') {
            b = Integer.parseInt(str.replace(str.charAt(0), '1'));
        }
        else {
            for (int i = 1;i < n;i++) {
                if (str.charAt(i) != '0'&&str.charAt(i) != '1') {
                    found = true;
                    b = Integer.parseInt(str.replace(str.charAt(i), '0'));
                    break;
                }
            }
            if (!found) b = num;
        }
        return a - b;
    }

    public int maximumDifference(int[] nums) {
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        int ret = 0;
        for (int num : nums) {
            ret = Math.max(ret, num - min);
            min = Math.min(min, num);
        }
        return ret == 0 ? -1 : ret;
    }

    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        int ret = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int x : set) {
            if (set.contains(x - 1)) {
                continue;
            }
            int y = x + 1;
            while (set.contains(y)) {
                y++;
            }
            ret = Math.max(ret, y - x);
        }
        return ret;
    }

    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) return s.length();
        int ret = 0;
        Set<Character> set = new HashSet<>();
        int start = 0, end = 0;
        while (start < s.length() && end < s.length()) {
            while (set.contains(s.charAt(end))) {
                set.remove(s.charAt(start));
                start++;
            }
            set.add(s.charAt(end++));
            ret = Math.max(ret, set.size());
        }
        return ret;
    }

    public int[][] divideArray(int[] nums, int k) {
        int n = nums.length;
        int[][] ret = new int[n/3][3];
        Arrays.sort(nums);
        for (int i = 0;i < n;i+=3) {
            if (nums[i + 2] - nums[i] > k) {
                return new int[0][];
            }
            ret[i/3][0] = nums[i];
            ret[i/3][1] = nums[i+1];
            ret[i/3][2] = nums[i+2];
        }
        return ret;

    }

    public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
        // write code here
        ArrayList<Integer> ret = new ArrayList<>();
        for (int i = 0;i < nums1.size();i++) {
            if (nums2.contains(nums1.get(i))&&!ret.contains(nums1.get(i))) {
                ret.add(nums1.get(i));
            }
        }
        return ret;
    }

    public static Read in = new Read();
    public static PrintWriter out = new PrintWriter(System.out);
    public static void main1(String[] args) throws IOException{
        String s = in.next();
        Stack<Character> st = new Stack<>();
        st.push(s.charAt(0));
        for (int i = 1;i < s.length();i++) {
            if (!st.isEmpty() && s.charAt(i) == st.peek()) {
                st.pop();
            }else {
                st.push(s.charAt(i));
            }
        }
        if (st.isEmpty()) out.print('0');
        else {
            Stack<Character> st2 = new Stack<>();
            while (!st.isEmpty()) {
                st2.push(st.pop());
            }
            while (!st2.isEmpty()) {
                out.print(st2.pop());
            }
        }
        out.close();
    }

    public static void main2(String[] args) throws IOException {
        int n = in.nextInt();
        int[] cost = new int[n];
        for (int i = 0; i < n; i++) {
            cost[i] = in.nextInt();
        }
        if (n == 1) out.println(cost[0]);
        else {
            int[] dp = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
            }
            out.println(dp[n]);
        }
        out.close();
    }

    public static void main3(String[] args) throws IOException {
        String s1 = in.next();
        String s2 = in.next();
        if (s1.length() > s2.length()) {
            String tmp = s1;
            s1 = s2;
            s2 = tmp;
        }
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        int index = -1, max = 0;
        for (int i = 1;i < n;i++) {
            for (int j = 1;j < m;j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        index = i;
                    }
                }
            }
        }
        out.println(s1.substring(index - max, index));
        out.close();
    }

    public static void main4(String[] args) throws IOException {
        int n = in.nextInt();
        int x = in.nextInt();
        int[] nums = new int[n + 1];
        for (int i = 1;i <= n;i++) {
            nums[i] = in.nextInt();
        }
        int[] sum = new int[n + 1];
        sum[1] = nums[1];
        for (int i = 2;i < n;i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        int minL = Integer.MAX_VALUE;
        int l = -1, r = -1;
        for (int i = 1;i <= n;i++) {
            for (int j = 0;j < i;j++) {
                if ((sum[i] - sum[j] >= x && (i - j + 1) < minL)
                        || ((i - j + 1) == minL && j < l)) {
                    l = j + 1;
                    r = i;
                    minL = i - j + 1;
                }
            }
        }
        out.println(l + " " + r);
        out.close();
    }

    public static void main5(String[] args) throws IOException {
        int n = in.nextInt();
        int x = in.nextInt();
        int[] nums = new int[n + 1];
        for (int i = 1;i <= n;i++) {
            nums[i] = in.nextInt();
        }
        int minL = Integer.MAX_VALUE;
        int l = -1, r = -1;
        int left = 1, right = 1;
        int sum = 0;
        while (right <= n) {
            sum += nums[right];
            while (sum >= x) {
                if ( (right - left + 1) < minL
                        || ((right - left + 1) == minL && left < l)) {
                    l = left;
                    r = right;
                    minL = right - left + 1;
                }
                sum -= nums[left++];
            }
            right++;
        }
        out.println(l + " " + r);
        out.close();
    }

    public static void main6(String[] args) throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n];
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
        long sum = 0;
        for (int i = 0;i < n;i++) {
            nums[i] = in.nextInt();
            if ((nums[i] & 1) == 1) {
                sum += nums[i];
            }else {
                q.offer(nums[i]);
            }
        }
        while (!q.isEmpty() && k > 0) {
            int num = q.poll();
            num /= 2;
            k--;
            if ((num & 1) == 1) {
                sum += num;
            }else {
                q.offer(num);
            }
        }
        while (!q.isEmpty()) {
            sum += q.poll();
        }
        out.println(sum);
        out.close();
    }

    static int[] dp = new int[10000001];
    public static void main7(String[] args) throws IOException {
        int n = in.nextInt();
        dp[1] = dp[2] = 1;
        for (int i = 3;i <= n;i++) {
            dp[i] = (dp[i - 1] % 10007) + (dp[i - 2] % 10007);
        }
        long ret = fb(n) % 10007;
        out.println(ret);
        out.close();
    }

    public static void main8(String[] args) throws IOException {
        int n = in.nextInt();
        int[][] ret = new int[n][n];
        for (int i = 0;i < n;i++) {
            ret[i][0] = 1;
            ret[i][i] = 1;
            for (int j = 1;j < i;j++) {
                ret[i][j] = ret[i - 1][j - 1] + ret[i - 1][j];
            }
        }
        for (int i = 0;i < n;i++) {
            for (int j = 0;j <= i;j++) {
                out.print(ret[i][j]);
                if (j != i) {
                    out.print(" ");
                }
            }
            out.println();
        }
        out.close();
    }
    public static long fb(int n) {
        if (n == 1 || n == 2) {
            return dp[n];
        }
        return dp[n - 1] + dp[n - 2];
    }

    int[] dx2 = {1,-1,0,0};
    int[] dy2 = {0,0,1,-1};
    boolean[][] vis;
    int n2, m2;
    public boolean exist (String[] board, String word) {
        // write code here
        n2 = board.length;
        m2 = board[0].length();
        vis = new boolean[n2][m2];
        for (int i = 0;i < n2;i++) {
            for (int j = 0;j < m2;j++) {
                boolean flag = false;
                if (board[i].charAt(j) == word.charAt(0)) {
                    flag = dfs(board, word, i, j, 0);
                    if (flag) return true;
                }
            }
        }
        return false;
    }
    public boolean dfs (String[] board, String word, int i, int j, int pos) {
        if (pos == word.length() - 1) {
            return true;
        }
        vis[i][j] = true;
        for (int k = 0;k < 4;k++) {
            int x = dx2[k] + i;
            int y = dy2[k] + j;
            if (x >= 0 && x < n2 && y >= 0 && y < m2 && board[x].charAt(y) == word.charAt(pos + 1) && !vis[x][y]) {
                if(dfs(board, word, x, y, pos + 1)) return true;
            }
        }
        vis[i][j] = false;
        return false;
    }

    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        // write code here
        int n = grid.size(), m = grid.get(0).size();
        boolean[][] vis = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid.get(i).get(j) == 2) {
                    q.offer(new int[] {i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int size = q.size();
            while(size-- > 0) {
                int[] t = q.poll();
                int i = t[0], j = t[1];
                for (int k = 0;k < 4;k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && grid.get(x).get(y) == 1) {
                        q.add(new int[] {x, y});
                        vis[x][y] = true;
                    }
                }
            }
            ret++;
        }
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid.get(i).get(j) == 1 && !vis[i][j]) {
                    return -1;
                }
            }
        }
        return ret - 1;
    }

    public int LastRemaining_Solution (int n, int m) {
        // write code here
        List<Integer> list = new ArrayList<>();
        for (int i = 0;i < n;i++) {
            list.add(i);
        }
        int pre = 0;
        while (list.size() > 1) {
            pre = (pre + m - 1) % list.size();
            list.remove(pre);
        }
        return list.get(0);
    }

    public String solve (String s, String t) {
        // write code here
        StringBuilder sb = new StringBuilder();
        int i = s.length() - 1, j = t.length() - 1;
        int tmp = 0;
        while (i >= 0 || j >= 0 || tmp != 0) {
            if (i >= 0) {
                tmp += s.charAt(i--) - '0';
            }
            if (j >= 0) {
                tmp += t.charAt(j--) - '0';
            }
            sb.append((char)(tmp % 10 + '0'));
            tmp /= 10;
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) throws IOException {
        String str = in.next();
        String tmp = "";
        String ret = "";
        for (int i = 0;i < str.length();i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                tmp = tmp + str.charAt(i) + "";
            }else {
                if (tmp.length() > ret.length()) {
                    ret = tmp;
                }
                tmp = "";
            }
        }
        if (str.charAt(str.length() - 1) >= '0' && str.charAt(str.length() - 1) <= '9' && tmp.length() > ret.length()) {
            ret = tmp;
        }
        out.println(ret);
        out.close();
    }

    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        head1 = reverse(head1);
        head2 = reverse(head2);
        int carry = 0;
        ListNode cur = new ListNode(-1);
        ListNode head = cur;
        while (head1 != null && head2 != null) {
            int sum = head1.val + head2.val + carry;
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            cur = cur.next;
            head1 = head1.next;
            head2 = head2.next;
        }
        while (head1 != null) {
            int sum = head1.val + carry;
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            head1 = head1.next;
            cur = cur.next;
        }
        while (head2 != null) {
            int sum = head2.val + carry;
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            head2 = head2.next;
            cur = cur.next;
        }
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return reverse(head.next);
    }
    public ListNode reverse (ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public String solve2 (String ss, String tt) {
        // write code here
        char[] s = new StringBuilder(ss).reverse().toString().toCharArray();
        char[] t = new StringBuilder(tt).reverse().toString().toCharArray();
        int n = s.length, m = t.length;
        int[] tmp = new int[n + m];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                tmp[i + j] += (s[i] - '0') * (t[j] - '0');
            }
        }
        int c = 0;
        StringBuilder sb = new StringBuilder();
        for (int num : tmp) {
            c += num;
            sb.append((char) ((c % 10) + '0'));
            c /= 10;
        }
        while (c > 0) {
            sb.append((char) (c % 10));
            c /= 10;
        }
        while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.reverse().toString();
    }

    public boolean isMatch(String str, String pat) {
        char[] s = str.toCharArray();
        char[] p = pat.toCharArray();
        int n = s.length, m = p.length;
        boolean[][] dp = new boolean[n+1][m+1];
        dp[n][m] = true;
        for (int i = m-1; i >= 0; i--) {
            dp[n][i] = i+1 < m&&p[i+1] == '*'&&dp[n][i+2];
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = m-1; j >= 0; j--) {
                if(j+1 == m||p[j+1] != '*') {
                    dp[i][j] = (p[j] == s[i]||p[j] == '.')&&dp[i+1][j+1];
                }else {
                    dp[i][j] = dp[i][j+2] || (p[j] == s[i]||p[j] == '.')&&dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
}

class Read {
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    public String next() throws IOException {
        while (!st.hasMoreTokens()) st = new StringTokenizer(bf.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
}

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      public TreeNode() {}
      public TreeNode(int val) { this.val = val; }
      public TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class RandomizedSet {
    int index = -1;
    Map<Integer, Integer> hash = new HashMap<>();
    int[] nums = new int[200010];
    Random rondom = new Random();

    public RandomizedSet() {

    }

    public boolean insert(int val) {
        if (hash.containsKey(val)) return false;
        nums[++index] = val;
        hash.put(val,index);
        return true;
    }

    public boolean remove(int val) {
        if (!hash.containsKey(val)) return false;
        int x = hash.remove(val);
        if (x != index) hash.put(nums[index], x);
        nums[x] = nums[index--];
        return true;
    }

    public int getRandom() {
        return nums[rondom.nextInt(index + 1)];
    }
}

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }